{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Repeating Character Replacement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: characterReplacement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #替换后的最长重复字符"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 和一个整数 <code>k</code> 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 <code>k</code> 次。</p>\n",
    "\n",
    "<p>在执行上述操作后，返回 <em>包含相同字母的最长子字符串的长度。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ABAB\", k = 2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>用两个'A'替换为两个'B',反之亦然。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"AABABBA\", k = 1\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "将中间的一个'A'替换为'B',字符串变为 \"AABBBBA\"。\n",
    "子串 \"BBBB\" 有最长重复字母, 答案为 4。\n",
    "可能存在其他的方法来得到同样的结果。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 仅由大写英文字母组成</li>\n",
    "\t<li><code>0 &lt;= k &lt;= s.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-repeating-character-replacement](https://leetcode.cn/problems/longest-repeating-character-replacement/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-repeating-character-replacement](https://leetcode.cn/problems/longest-repeating-character-replacement/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ABAB\"\\n2', '\"AABABBA\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        res = 0\n",
    "        hash_map = {} \n",
    "        flag = True\n",
    "        while r < len(s):\n",
    "            if flag == True:\n",
    "                hash_map[s[r]] = hash_map.get(s[r], 0) + 1\n",
    "            ind = r - l +1 - max(hash_map.values())\n",
    "            if ind <=k:\n",
    "                res = max(res, r-l+1)\n",
    "                r+=1\n",
    "                flag = True\n",
    "            else:\n",
    "                hash_map[s[l]] -= 1   \n",
    "                l+=1\n",
    "                flag = False\n",
    "            \n",
    "                       \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def find_max(self,arr):\n",
    "        j,val=-1,-1\n",
    "        for i,v in enumerate(arr):\n",
    "            if v>val:\n",
    "                val=v\n",
    "                j=i\n",
    "        return j\n",
    "    def characterReplacement(self, s, k):\n",
    "        if s=='':\n",
    "            return 0\n",
    "        arr=[0 for _ in range(26)]\n",
    "        orda=ord('A')\n",
    "        width=k+1\n",
    "        i=0\n",
    "        max_len=k\n",
    "        for c in s[:width]:\n",
    "            arr[ord(c)-orda]+=1\n",
    "        while True:\n",
    "            j=self.find_max(arr)\n",
    "            if width-arr[j]<=k:\n",
    "                max_len=max(max_len,width)\n",
    "                if i+width<len(s):\n",
    "                    arr[ord(s[i+width])-orda]+=1\n",
    "                    width+=1\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                arr[ord(s[i])-orda]-=1\n",
    "                i+=1\n",
    "                width-=1\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s, k):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count, n, ans, i = [0] * 26, len(s), 0, 0\n",
    "        for j in range(n):\n",
    "            count[ord(s[j]) - 65] += 1\n",
    "            while j - i + 1 - max(count) > k:\n",
    "                count[ord(s[i]) - 65] -= 1\n",
    "                i += 1\n",
    "            ans = max(ans, j - i + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        max_len = 0\n",
    "        counter = [0] * 26\n",
    "        i = -1\n",
    "        for j in range(len(s)):\n",
    "            l = ord(s[j]) - ord('A')\n",
    "            counter[l] += 1\n",
    "            while j - i - max(counter) > k:\n",
    "                # shrink window\n",
    "                i += 1\n",
    "                l = ord(s[i]) - ord('A')\n",
    "                counter[l] -= 1\n",
    "            max_len = max(max_len, j - i)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        # 用字典保存字母出现的次数，需要替换的字符数目＝窗口字符数目－数量最多的字符数目\n",
    "        letter_num = {}\n",
    "        l = 0\n",
    "        res = 0\n",
    "        for r in range(len(s)):\n",
    "            # 字典保存字符出现的次数\n",
    "            letter_num[s[r]] = letter_num.get(s[r], 0) + 1\n",
    "            # 找到出现次数最多的字符\n",
    "            max_letter = max(letter_num, key=letter_num.get)\n",
    "            # 如果替换的字符数目超过给定的k，则移动左边界\n",
    "            while r - l + 1 - letter_num[max_letter] > k:\n",
    "                letter_num[s[l]] -= 1\n",
    "                l += 1\n",
    "                # 需要更新最多个数的字符\n",
    "                max_letter = max(letter_num, key=letter_num.get)\n",
    "            # 如果s[r]　超出了替换的字符数目，需要先处理，再计算结果\n",
    "            res = max(res, r - l + 1)\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        # s = \"AAAB\"\n",
    "        # k = 0\n",
    "        from collections import Counter\n",
    "        look_up = Counter()\n",
    "        start = 0\n",
    "        end = 0\n",
    "        count = 0\n",
    "        ans = 0\n",
    "        while end<len(s):\n",
    "            look_up[s[end]] += 1\n",
    "            end += 1\n",
    "            # sorted(look_up, key = lambda x : x[0])\n",
    "            count = end - start - look_up.most_common(1)[0][1]\n",
    "            # print(start,end, look_up.most_common(1)[0][1],count)\n",
    "            while count > k:\n",
    "                # print(start,end,count)\n",
    "                if end-1-start>ans:\n",
    "                    ans = end - start-1\n",
    "                look_up[s[start]] -= 1\n",
    "                start += 1\n",
    "                count = end - start - look_up.most_common(1)[0][1]\n",
    "        if end-start>ans:\n",
    "            ans = end - start\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        l, r = 0, min(k, n)\n",
    "\n",
    "\n",
    "        calc = {}\n",
    "        for i in range(l, r):\n",
    "            calc[s[i]] = calc.get(s[i], 0) + 1\n",
    "\n",
    "        while True:\n",
    "            max_count = max(calc.values() or [0])\n",
    "\n",
    "            if r - l <= max_count + k: # 窗口扩大到当前最大加一\n",
    "                if r == n:\n",
    "                    return r - l\n",
    "\n",
    "                calc[s[r]] = calc.get(s[r], 0) + 1\n",
    "                r += 1\n",
    "            else:  # 移动窗口\n",
    "                if r == n:\n",
    "                    return r - l - 1\n",
    "\n",
    "                calc[s[r]] = calc.get(s[r], 0) + 1\n",
    "                calc[s[l]] = calc[s[l]] - 1\n",
    "\n",
    "                r += 1\n",
    "                l += 1\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        window = {}\n",
    "        i, j, max_len = 0, 0, 0\n",
    "        for j in range(len(s)):\n",
    "            c1 = s[j]\n",
    "            window[c1] = window.get(c1, 0) + 1\n",
    "            while (j - i + 1) - max(window.values()) > k: \n",
    "                #取此此区间内出现最多的元素为基准 此时要改动的元素就是最少的 如果要改动的元素多于k 开始缩小区间\n",
    "                c2 = s[i]\n",
    "                i = i + 1\n",
    "                window[c2] = window[c2] - 1\n",
    "                if window[c2] == 0:\n",
    "                    del window[c2]\n",
    "            cur_len = j - i + 1\n",
    "            if cur_len > max_len:\n",
    "                max_len = cur_len\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        start = 0\n",
    "        end = 0\n",
    "        num = 0\n",
    "        res = 0\n",
    "        dictstr = defaultdict(int)\n",
    "        for end in range(len(s)):\n",
    "            right = s[end]\n",
    "            dictstr[right] = dictstr[right] + 1\n",
    "            num = max(num,dictstr[right])\n",
    "            if (end - start + 1 - num)>k:\n",
    "                left = s[start]\n",
    "                start = start + 1\n",
    "                dictstr[left] = dictstr[left] - 1\n",
    "            res = max(res,end-start+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        char_counter = defaultdict(int)  # 当前窗口内各字符数量，因为窗口是动态的，所以用哈希表可以更好维护\n",
    "        \n",
    "        left = right = 0  # 初始化动态窗的左、右指针\n",
    "        max_freq = 0  # 当前窗口内出现最多字符的频数\n",
    "\n",
    "        while right < len(s):  # 终止条件：右指针移动到最右\n",
    "            char_counter[s[right]] += 1\n",
    "            max_freq = max(max_freq, char_counter[s[right]])\n",
    "\n",
    "            if (right - left + 1) - max_freq > k:  # 可替换次数k不足以将当前窗内所有字符都替换成最高频字符，滑动\n",
    "                char_counter[s[left]] -= 1  # 左指针右移前，先删除窗口最左字符在窗口内的计数\n",
    "                left += 1\n",
    "            # else: 扩充，但扩充不需要更多额外的操作\n",
    "            right += 1\n",
    "        return right - left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        # slen = len(s)\n",
    "        # maxLen = 0\n",
    "        # for i in range(0,slen):\n",
    "        #     if maxLen >=int(slen/2):\n",
    "        #         return maxLen\n",
    "        #     repeatedDic = {}\n",
    "        #     thisTimeLen = 0\n",
    "        #     for j in range(i,slen):\n",
    "        #         repeatedDic[s[j]] = repeatedDic.get(s[j],0)+1\n",
    "        #         maxValue = max(list(repeatedDic.values()))\n",
    "        #         if j-i+1 -maxValue > k:\n",
    "        #             break\n",
    "        #         thisTimeLen = j-i+1\n",
    "        #     maxLen = max(maxLen,thisTimeLen)\n",
    "        # return maxLen\n",
    "                # slen = len(s)\n",
    "        slen = len(s)\n",
    "        if slen < 1:\n",
    "            return 0\n",
    "        head=tail=0\n",
    "        maxLen = 0\n",
    "        repeatedDic={s[0]:1}\n",
    "        while tail < slen  and (maxLen <= slen - head): \n",
    "             maxValue = max(list(repeatedDic.values()))\n",
    "             if tail - head+1-maxValue > k:\n",
    "                 repeatedDic[s[head]]-=1\n",
    "                 head+=1\n",
    "             else:\n",
    "                 maxLen = max(maxLen,tail-head+1)\n",
    "                 tail+=1\n",
    "                 if tail < slen:\n",
    "                    repeatedDic[s[tail]] = repeatedDic.get(s[tail],0)+1\n",
    "        return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        window= defaultdict(int)\n",
    "        l,r,count,length=0,0,0,0\n",
    "        while r<len(s):\n",
    "            c=s[r]\n",
    "            window[c]+=1\n",
    "            count =max(count,window[c])\n",
    "            print(l,r)\n",
    "\n",
    "            while r-l+1-count>k:\n",
    "                d=s[l]\n",
    "                l+=1\n",
    "                window[d]-=1\n",
    "            length = max(r - l + 1, length)\n",
    "            r += 1\n",
    "        return length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            d[c].append(i)\n",
    "        m = 0\n",
    "        for a in d.values():\n",
    "            i = 0\n",
    "            for j in range(m + 1, len(a)):\n",
    "                if j - i <= m:\n",
    "                    continue\n",
    "                t = a[j] - j - k\n",
    "                while a[i] - i < t:\n",
    "                    i += 1\n",
    "                m = max(m, j - i)\n",
    "        return min(len(s), m + k + 1)\n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        se = set(s)\n",
    "        sl = len(s)\n",
    "        if sl <= 1:\n",
    "            return sl\n",
    "        max_len = 1\n",
    "        for i in se:\n",
    "            ki = [j for j in range(sl) if s[j] != i]\n",
    "            kl = len(ki)\n",
    "            if kl <= k:\n",
    "                return sl\n",
    "            temp_len = max(ki[k], sl - ki[-k - 1] - 1)\n",
    "            for j in range(kl - 1 - k):\n",
    "                temp_len = max(ki[j + k + 1] - ki[j] - 1, temp_len)\n",
    "            max_len = max(max_len, temp_len)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        length = len(s)\n",
    "        if length == 0:\n",
    "            return 0\n",
    "\n",
    "        c = Counter()\n",
    "        left = 0\n",
    "        res = float('-inf')\n",
    "        for right in range(length):\n",
    "            c[s[right]] += 1\n",
    "            while (right - left + 1) - c.most_common()[0][1] > k:\n",
    "                c[s[left]] -= 1\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        # # 核心思想：除了出现次数最多的字符以外，[left,right]之间其他字符的数量之和不超过k个\n",
    "        # from collections import Counter\n",
    "        # left = ans = 0\n",
    "        # count = Counter()\n",
    "        # n = len(s)\n",
    "        # sum_res = 0\n",
    "        \n",
    "        # for right in range(n):\n",
    "        #     count[s[right]] += 1\n",
    "        #     sum_res += 1\n",
    "        #     res_value = sum_res - max(count.values())\n",
    "        #     while res_value > k:\n",
    "        #         count[s[left]] -= 1\n",
    "        #         sum_res -= 1\n",
    "        #         left += 1\n",
    "        #         res_value = sum_res - max(count.values())\n",
    "        #     ans = max(ans, right-left+1)\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        from collections import Counter\n",
    "        s_len = len(s)\n",
    "        left = ans = 0\n",
    "        count = Counter()\n",
    "        sum_res = 0\n",
    "        for right in range(s_len):\n",
    "            count[s[right]] += 1\n",
    "            sum_res += 1\n",
    "            diff_res = sum_res-max(count.values())\n",
    "            while(diff_res > k):\n",
    "                count[s[left]] -= 1\n",
    "                sum_res -= 1\n",
    "                left += 1\n",
    "                diff_res = sum_res-max(count.values())\n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        # maxCnt 保存滑动窗口内相同字母出现次数的历史最大值, 所以 maxCnt + k 是出现过的最大重复字符串数\n",
    "        # 窗口的大小保持单调递增, 窗口的不变和扩张. 窗口大小始终维持最大重复字符串数 因为比这小的也是没有意义的\n",
    "        # 窗口的宽度 maxCnt + k < (r - l + 1) => 窗口不变\n",
    "        # 窗口的宽度 maxCnt + k >= (r - l + 1) => 窗口增加\n",
    "        ans = l = maxCnt = 0\n",
    "        cntMap = defaultdict(int)\n",
    "        for r, c in enumerate(s):\n",
    "            cntMap[c] += 1\n",
    "            maxCnt = max(maxCnt, cntMap[c])\n",
    "            if maxCnt + k < r - l + 1:\n",
    "                cntMap[s[l]] -= 1\n",
    "                l += 1\n",
    "            ans = r - l + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        num = [0] * 26\n",
    "        n = len(s)\n",
    "        left, right = 0, 0\n",
    "        Max = 0\n",
    "\n",
    "        while right < n:\n",
    "            num[ord(s[right]) - ord(\"A\")] += 1\n",
    "            Max = max(Max, num[ord(s[right]) - ord(\"A\")])\n",
    "            if right - left + 1 > k + Max:\n",
    "                num[ord(s[left]) - ord(\"A\")] -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        \n",
    "        return right - left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        A = ord('A')\n",
    "        freq = [0]*26\n",
    "        maxCount = 0\n",
    "        res = 0\n",
    "        while right<len(s):\n",
    "            freq[ord(s[right])-A] += 1\n",
    "            maxCount = max(maxCount,freq[ord(s[right])-A])\n",
    "            right += 1\n",
    "\n",
    "            if right-left > maxCount+k:\n",
    "                freq[ord(s[left])-A] -= 1\n",
    "                left += 1\n",
    "            print(\"111:\",right-left)\n",
    "            res = max(res, right-left)\n",
    "            print(\"res:\",res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        start = 0\n",
    "        end = 0\n",
    "        el_map = {}\n",
    "        res = []\n",
    "        for char in s:\n",
    "            if char not in el_map.keys():\n",
    "                el_map[char] = 0\n",
    "\n",
    "        def handler(el_map, k):\n",
    "            el_list = sorted(el_map.items(), key = lambda x:x[1], reverse = True)\n",
    "            if k < sum(el_map.values()) - el_list[0][1]:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        while(end < len(s)):\n",
    "            el_map[s[end]] += 1\n",
    "            while(handler(el_map, k)):\n",
    "                el_map[s[start]] -= 1\n",
    "                start += 1\n",
    "            res.append(end - start +1)\n",
    "            end += 1\n",
    "        return max(res)\n",
    "# print(Solution().characterReplacement(s = \"ABAB\", k = 2))\n",
    "# print(Solution().characterReplacement(s = \"AABABBA\", k = 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        nums = [0 for _ in range(26)]\n",
    "        maxn, left, right = 0, 0, 0\n",
    "\n",
    "        while right < n:\n",
    "            index = ord(s[right]) - ord('A')\n",
    "\n",
    "            nums[index] += 1\n",
    "            maxn = max(maxn, nums[index])\n",
    "            if right - left + 1 - maxn > k:\n",
    "\n",
    "                nums[ord(s[left]) - ord('A')] -= 1\n",
    "\n",
    "                maxn = max(nums)\n",
    "                left += 1\n",
    "            \n",
    "            right += 1\n",
    "\n",
    "        return right - left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        count = {}\n",
    "        \n",
    "        l = 0\n",
    "        maxf = 0\n",
    "        for r in range(len(s)):\n",
    "            count[s[r]] = 1 + count.get(s[r], 0)\n",
    "            maxf = max(maxf, count[s[r]])\n",
    "\n",
    "            if (r - l + 1) - maxf > k:\n",
    "                count[s[l]] -= 1\n",
    "                l += 1\n",
    "\n",
    "        return (r - l + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def characterReplacement(self, s: str, k: int) -> int:\n",
    "        l = 0\n",
    "        r = 0\n",
    "        n = len(s)\n",
    "        cnt = {}\n",
    "        res = 0\n",
    "        max_cnt = 0\n",
    "        while r < n:\n",
    "            cnt[s[r]] = cnt.get(s[r],0) + 1 \n",
    "            max_cnt = max(max_cnt, cnt[s[r]])\n",
    "            r += 1\n",
    "            while r-l-max_cnt > k:\n",
    "                cnt[s[l]] -= 1\n",
    "                if cnt[s[l]] == 0:\n",
    "                    cnt.pop(s[l])\n",
    "                l += 1\n",
    "            res = max(res,r-l)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
